Various methods for rendering an arbitrary polygon have been developed. The methods include (1) a point-based method, (2) a raster-line-based method, (3) a triangle-based method, and (4) a stencil-buffer-based method.
The method (1) is a method for determining rendering with regard to respective points (pixels) included in a rendering area and performing rendering operation on a per-point (pixel) basis. In order to speed up rendering operation, various contrivances, such as deletion of useless rendering areas or simplifying a determination of a drawing at each of the points, have been conceived. Moreover, in order to achieve a speedup in rendering, the function is often embodied in the form of hardware. One device into which the method is embodied as hardware is called a rasterizer (see, e.g., the background-art document 1 listed below). This method is simple and hence is characterized by very stable operation, but has a drawback of a necessity for making a determination of rendering for each point, thereby entailing very high processing cost. For this reason, the function is typically embodied as custom-designed hardware.
The method (2) corresponds to an improvement on the method (1). The method (2) is analogous to the method (1) in that a drawing is determined on a per-dot basis or within a range corresponding to each dot. However, when rendering is performed, rendering portions in the respective points are collected, and the thus-collected rendering portions are replaced with line drawings of respective scan lines of a screen on which rendering is desired to be effected. Thus, in relation to determination of a drawing, the method (2) entails high processing cost, as does the method (1). However, cost of rendering operation is curtailed, and hence the method (2) is expected to become faster than the method (1). Determining a drawing entails processing performed by a processing system having a high-speed CPU or realization of processing in the form of custom-designed hardware. A general-purpose graphics LSI (GPU) can be used for rendering operation. The reason for this is that the graphics LSI has the function of rendering lines and triangles at high speed. For this reason, the method (2) can be said to have enhanced versatility as compared with the method (1).
The method (3) is for dividing a polygon desired to be drawn into a group of triangles and rendering the polygon from triangles (see, e.g., the background-art document 2 listed below). This intends to achieve a speedup on the premise of the use of a general-purpose graphics LSI or a high-speed triangle rendering apparatus (because the graphics LSI has the function of rendering lines and triangles at high speed). Therefore, the method (3) is superior to the methods (1) and (2) in terms of versatility. However, triangulation requires complicated processing, and hence stability of complicated processing may pose a problem. When a polygon desired to be drawn has a very complicated shape, there also arises a problem of triangulation processing involving a very large cost. Since the method is based on the premise that a group of triangles are rendered by use of a graphics LSI or the like, the LSI cannot be used when it has insufficient resources. The reason for this is that the polygon must be divided into a group of triangles; and that the thus-divided triangles must be fed to the graphics LSI, which in turn entails a comparative increase in the volume of usage of memory.
The method (4) is completely based on usage of a general-purpose graphics LSI, and polygon rendering is implemented by use of a function called a stencil buffer provided in the graphics LSI (see, e.g., the background-art document 3 listed below). This method enables more stable and faster polygon rendering than that provided by any one of the methods (1) through (3). However, the method entails full usage of the features of the graphics LSI, and hence there arises a problem of a necessity for a large amount of resource of the graphics LSI.
As mentioned above, in relation to the methods (1) through (4), a tradeoff exists between a processing speed and required resources. Therefore, in a case where resources, such as a graphics LSI, are utilized by a plurality of tasks, the respective methods raise problems. In relation to the methods (1) and (2), required resources are small in amount, and hence processing can be performed stably regardless of variations in resources. However, difficulty is encountered in effecting high-speed processing, because of a large volume of processing. In relation to the methods (3) and (4), when sufficient resources are available, high-speed processing is feasible. However, when the resources are made deficient by other tasks, there arises a problem of a drop in processing performance or a problem of a failure to execute processing for reasons of a deficiency in resources.
As mentioned above, the related art methods have drawbacks in terms of processing speed and stable operation induced by variations in resources as a result of execution of a plurality of tasks.
Background-Art Document 1:
Renate Kempf and Chris Frazier, “The Open GL Processing Pipeline,” Chapter 2: Overview of Commands and Routines, Open GL Reference Manual Second Edition, ISBN 0-201-46140-4, pp. 8 to 16, 1997.
Background-Art Document 2:
Mark de Berg, Mare van Kreveld, Mark Overmars, and Otfried Schwartzkopf “Computational Geometry,” ISBN 4-7649-0277-X, pp. 44 to 61, Kindai Kagakusha Co., Ltd., 2000.
Background-Art Document 3:
Jackie Neider, Tom Davis, Mason Woo, “Drawing filled, Concave Polygons Using the Stencil Buffer,” Chapter 13: Now That You Know, OpenGL programming Guide, ISBN 0-201-63274-8, pp. 398-399, 1993.